package com.feiyue.learning.recursive;

/**
 * xxx + xxx = xxx (1-9唯一, 满足表达式)
 * @author  feiyue
 * @date  2020/4/5
 */
public class FillInExpression {

    private static int count = 0;

    // aux[i] = 1 表示数字 i 已被占用, aux[i] = 0 表示数字 i 未被使用
    private static int[] aux = new int[10];

    public static void main(String[] args) {
        int[] numbers = new int[10];
        recursiveFillIn(numbers, 1);
        System.out.println("满足表达式的总数：" + count / 2);
    }

    /**
     * 深度优先遍历, 完成表达式各个数字的尝试
     * @author feiyue
     * @date 2020/4/5 13:57
     * @param numbers : 表示数字填写情况(index_0 弃用)
     * @param position : 表示在填写第几个数字
     */
    private static void recursiveFillIn(int[] numbers, int position) {
        if (position == 10) {
            if ((numbers[1] + numbers[4]) * 100
                    + (numbers[2] + numbers[5]) * 10
                    + (numbers[3] + numbers[6]) == (numbers[7] * 100 + numbers[8] * 10 + numbers[9])) {
                count++;
                System.out.println(numbers[1] + "" + numbers[2] + "" + numbers[3]
                        + " + " + numbers[4] + "" + numbers[5] + "" + numbers[6]
                        + " = " + numbers[7] + "" + numbers[8] + "" + numbers[9]);
            }
            return;
        }

        // 表达式数字选择依次1->9, 如果已经选了则选择后续的；每次遍历完需要考虑是否还可以其他后续选择
        for (int i = 1; i < numbers.length; i++) {
            if (aux[i] == 0) {
                numbers[position] = i;
                aux[i] = 1;
                recursiveFillIn(numbers, position + 1);

                // 回退重新选择
                aux[i] = 0;
            }
        }
    }
}
